package algorithm;

import java.util.HashMap;
import java.util.Map;

public class leetcode_0076 {
    public String minWindow(String s, String t) {
        char[] list=t.toCharArray();
        int lent=t.length();
        int len=s.length();
        if(lent>len||lent==0) return "";
        if(len==1){
            if(s.equals(t)) return s;
            else return "";
        }
        int [] origin=new int[52];
        for(int i=0;i<lent;++i){
           if(list[i]>='a'&&list[i]<='z'){
               origin[list[i]-'a']+=1;
           }
           else{
               origin[list[i]-'A'+26]+=1;
           }
        }
        int minlen=len+1;
        int start=0;
        int left=0;
        remove(origin,s.charAt(0));
        if(all(origin)) return s.charAt(0)+"";
        for(int i=1;i<len;++i){
            remove(origin,s.charAt(i));
            while(all(origin)){
                if(minlen>i-left+1){
                    minlen=i-left+1;
                    start=left;
                }
                add(origin,s.charAt(left));
                left++;
            }
        }
        if(minlen==len+1) return "";
        return s.substring(start,start+minlen);
    }
    public boolean all(int[] origin){
        for(int i=0;i<52;++i){
            if(origin[i]>0) return false;
        }
        return true;
    }
    public void add(int[] origin,char a){
        if(a>='a'&&a<='z'){
            origin[a-'a']+=1;
        }
        else{
            origin[a-'A'+26]+=1;;
        }
    }
    public void remove(int[] origin,char a){
        if(a>='a'&&a<='z'){
            origin[a-'a']-=1;
        }
        else{
            origin[a-'A'+26]-=1;;
        }
    }
}
